package com.example.leetcode.sort.common;

import javafx.util.Pair;
import lombok.extern.slf4j.Slf4j;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

@Slf4j
public class SortUtils {

    private static final Logger logger = LoggerFactory.getLogger(SortUtils.class);

    /**
     * 冒泡排序
     *
     * @param array
     */
    public static void bubbleSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        // 走 n-1 趟，每一趟排好一个数
        for (int i = 0; i < array.length - 1; i++) {
            // 默认不需要执行下一趟
            boolean flag = false;
            // 从后往前找数, j所指的数为当前的数
            for (int j = array.length - 1; j >= i + 1; j--) {
                // j 所指的数与它前一个数比较  实现的是升序
                if (array[j] < array[j - 1]) {
                    swap(array, j - 1, j);
                    flag = true;
                }
            }
            System.out.printf("第 %d 趟后结果", i + 1);
            System.out.println(Arrays.toString(array));
            // 如果当前这一趟没有发生交换, 说明数据已经有序了, 可以结束程序了
            if (flag == false) {
                break;
            }
        }
    }

    /**
     * 选择排序
     *
     * @param array
     */
    public static void selectSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        for (int i = 0; i < array.length - 1; i++) {
            int curBest = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[curBest]) {
                    curBest = j;
                }
            }
            if (curBest != i) {
                swap(array, curBest, i);
            }
            System.out.printf("第 %d 趟后结果", i + 1);
            System.out.println(Arrays.toString(array));
        }
    }

    /**
     * 插入排序
     *
     * @param array
     */
    public static void insertSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        for (int i = 1; i <= array.length - 1; i++) {
            // 先将当前需要排序的值备份
            int temp = array[i];
            int j = i - 1;
            // 从当前位置往前循环挪动元素
            while (j >= 0) {
                // 前方某个元素比当前元素大，则往后移动一个位置
                if (array[j] > temp) {
                    array[j + 1] = array[j];
                    j--;
                } else {
                    break;
                }
            }
            // 前面元素移动完成，将当前排序元素插入
            array[j + 1] = temp;
            System.out.printf("第 %d 趟后结果", i);
            System.out.println(Arrays.toString(array));
        }
    }

    private static void swap(int[] array, int first, int second) {
        if (first == second) {
            return;
        }
        int temp = array[second];
        array[second] = array[first];
        array[first] = temp;
    }

    public static long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(gifts.length, Comparator.reverseOrder());
        for (int gift : gifts) {
            pq.offer(gift);
        }
        for (int i = 0; i < k; i++) {
            pq.offer((int) Math.sqrt(pq.poll()));
        }
        return pq.stream().mapToLong(Integer::intValue).sum();
    }

    public static List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> ans = new ArrayList<>();
        ans.add(folder[0]);
        for (int i = 1; i < folder.length; ++i) {
            int pre = ans.get(ans.size() - 1).length();
            if (!(pre < folder[i].length() && ans.get(ans.size() - 1).equals(folder[i].substring(0, pre)) && folder[i].charAt(pre) == '/')) {
                ans.add(folder[i]);
            }
        }
        return ans;
    }

    public static int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public static void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }

    public static void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }


    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.offer(entry);
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = queue.poll().getKey();
        }
        return result;
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        // 暴力解法 直接使用优先队列会超时
//        int left = 0;
//        int right = k - 1;
//        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
//        for(int i = left; i<= right; i++){
//            queue.add(nums[i]);
//        }
//        List<Integer> list = new ArrayList<>();
//        while(right <= nums.length -1){
//            // 先计算区间的最大值
//            list.add(queue.peek());
//            // 根据最左侧元素的值，从队列中移除一个值
//            queue.remove(nums[left]);
//            right ++;
//            if(right <= nums.length - 1){
//                queue.add(nums[right]);
//                left ++;
//            }
//        }
//        return ArrayUtils.convertListToArray(list);

        int n = nums.length;
        // 先按值降序排序,值相等按下标降序排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]);
        for (int i = 0; i < k; ++i) {
            // 初始化队列
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        // 将当前堆顶元素加入结果集
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            // 将窗口右侧加入的新元素入队
            pq.offer(new int[]{nums[i], i});
            // 判断堆顶元素是否位于窗口内,不在窗口内则移除
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            // 去掉所有不在窗口中的堆顶元素,此时的堆顶元素就是窗口内的最大值
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }

    public static int nthUglyNumber(int n) {
        PriorityQueue<Long> queue = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        queue.add(1L);
        set.add(1L);
        int[] fac = {2, 3, 5};
        for (int i = 0; i < n - 1; i++) {
            Long num = queue.poll();
            set.remove(num);
            for (int j = 0; j < fac.length; j++) {
                long newNum = fac[j] * num;
                if (!set.contains(newNum)) {
                    queue.add(newNum);
                    set.add(newNum);
                }
            }
        }
        return Math.toIntExact(queue.poll());
    }

    public static int[] sortArray(int[] nums) {
        randomizedQuicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public static void randomizedQuicksort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = randomizedPartition(nums, l, r);
            randomizedQuicksort(nums, l, pos - 1);
            randomizedQuicksort(nums, pos + 1, r);
        }
    }

    public static int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    public static int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    public static int[] myQuickSortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        // 返回的index是当前排序好的那个选取的主元的下标，而不是一开始主元一开始存在的位置，而是排序完成后所在的位置
        int index = partition2(nums, left, right);
        quickSort(nums, left, index - 1);
        quickSort(nums, index + 1, right);
    }

    private static int getPivotIndex(int left, int right) {
        Random random = new Random();
        return random.nextInt(right - left + 1) + left;
    }

    private static int partition2(int[] nums, int left, int right) {
        int index = getPivotIndex(left, right);
        // 当前排序的元素
        int pivot = nums[index];
        // 将随机获取的主元放到最右侧
        swap(nums, index, right);
        int i = left;
        // 此处必须从前往后找小的，这样交换时，无需再去找大的，i的位置一定是较大值
        for (int j = left; j <= right - 1; j++) {
            if (nums[j] < pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        // 在for循环中加了1，不用再重复+1
        swap(nums, i, right);
//        logger.info("在 {} 和 {} 范围内排序，pivot元素为 {} 处的 {}, 排好位置为 {}, 数组为 {}", left, right, index, pivot, i, nums);
        // 返回pivot元素的下标
        return i;
    }

    public static String[] findRelativeRanks(int[] score) {
        String[] grade = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getKey() - o1.getKey());
        for (int i = 0; i < score.length; i++) {
            queue.offer(new Pair<>(score[i], i));
        }
        int n = queue.size();
        String[] ans = new String[n];
        for (int i = 0; i < n; i++) {
            Integer index = queue.poll().getValue();
            if (i == 0) {
                ans[index] = grade[0];
                continue;
            }
            if (i == 1) {
                ans[index] = grade[1];
                continue;
            }
            if (i == 2) {
                ans[index] = grade[2];
                continue;
            }
            ans[index] = String.valueOf(i + 1);
        }
        return ans;
    }

    public static int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < stones.length; i++) {
            queue.add(stones[i]);
        }
        while (queue.size() > 1) {
            int x = queue.poll();
            ;
            int y = queue.poll();
            queue.add(Math.abs(x - y));
        }
        return queue.poll();
    }

    public static int[] kWeakestRows(int[][] mat, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            int[] first = mat[o1];
            int[] second = mat[o2];
            int countOne = (int) Arrays.stream(first).filter(x -> x == 1).count();
            int countTwo = (int) Arrays.stream(second).filter(x -> x == 1).count();
            if (countOne != countTwo) {
                return countOne - countTwo;
            } else {
                return o1 - o2;
            }
        });
        for (int i = 0; i < mat.length; i++) {
            queue.add(i);
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll();
        }
        return ans;
    }

    public static String[] sortPeople(String[] names, int[] heights) {
        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < heights.length; i++) {
            map.put(heights[i], names[i]);
        }
        heights = Arrays.stream(heights).boxed().sorted((o1, o2) -> o2 - o1).mapToInt(x -> x).toArray();
        String[] ans = new String[heights.length];
        for (int i = 0; i < heights.length; i++) {
            ans[i] = map.get(heights[i]);
        }
        return ans;
    }
}
